#include "Graph.hpp"
#include "UnDirGraph.hpp"
#include "DijkstraTable.hpp"
#include "PrimData.hpp"
#include "iostream"
#include "map"
#include "vector"


void test01();
void test02();
void test03(); //测试完成
void test04(); //Floyd算法测试
void test05(); //prim算法
void test06(); //Bellman算法,处理负权,但是算法效率低
void test07(); //Kruskal算法
void test08(); //检测是否有环
void test09();// Ford-Fulkerson算法
void test10();// 测试匈牙利算法

void test01()
{
    Graph<char,double> G(std::vector<char> {'a','b','c','d','e'});

    G.addEdgesFrom({'a','b','c'},{'c','d','e'},1);
    G.addEdge('a','b',1);
    G.addEdgesFrom({'d','e'},{'e','d'},1);
    G.addEdge('b','e',1);
    G.addEdge('b','a',1);
    G.undirected();
    G.write2Dot("test01.dot");
    G.BFS();
}

void test02()
{
    // 测试深度优先算法
    Graph<int,int> G({0,1,2,3,4,5,6,7,8,9});
    G.addEdgesFrom({0,0,1,1,3,5,5,5,8,1},{1,2,4,3,5,6,7,8,9,2},1);
    G.undirected(); // 变成无向图
    G.write2Dot("../test02.dot");
    G.Draw();
}

void test03()
{
    //测试 Dijkstra算法
    Graph<char,int> G({'1','2','3','4','5','6','7'});
    G.addEdge('3','1',4);
    G.addEdge('3','6',5);
    G.addEdge('1','2',2);
    G.addEdge('1','4',1);
    G.addEdge('4','3',2);
    G.addEdge('4','6',8);
    G.addEdge('4','7',4);
    G.addEdge('4','5',2);
    G.addEdge('2','4',3);
    G.addEdge('2','5',10);
    G.addEdge('5','7',1);
    G.addEdge('7','6',1);
    G.write2Dot("../test03.dot");
    auto vec =  G.Dijkstra('3','5');
    for(auto p :vec){
        std::cout << p << " ";
    }

}

void test04()
{
    //测试 Floyd算法
    Graph<char,int> G({'1','2','3','4','5','6','7'});
    G.addEdge('3','1',4);
    G.addEdge('3','6',5);
    G.addEdge('1','2',2);
    G.addEdge('1','4',1);
    G.addEdge('4','3',2);
    G.addEdge('4','6',8);
    G.addEdge('4','7',4);
    G.addEdge('4','5',2);
    G.addEdge('2','4',3);
    G.addEdge('2','5',10);
    G.addEdge('5','7',1);
    G.addEdge('7','6',1);

    auto mat = G.Floyd();
    for(int i = 0;i < mat.size() ; i++){
        for(int j = 0; j < mat.size() ; j++){
            std::cout <<"(" << i << "," << j << ") :" << mat[i][j] << std::endl;
        }
    }
}
void test05()
{
    UnDirGraph<char,int> G({'1','2','3','4','5','6','7'});
    G.addEdge('1','2',2);
    G.addEdge('1','3',4);
    G.addEdge('1','4',1);
    G.addEdge('2','4',3);
    G.addEdge('2','5',10);
    G.addEdge('3','4',2);
    G.addEdge('3','6',5);
    G.addEdge('4','5',7);
    G.addEdge('4','6',8);
    G.addEdge('4','7',4);
    G.addEdge('5','7',6);
    G.addEdge('6','7',1);
    G.write2Dot("../test05.dot");
    G.print();
    auto min_tree = G.Prim();
    min_tree.write2Dot("../test05_2.dot");
}

void test06()
{
    Graph<char,int> G({'0','1','2','3','4'});
    G.addEdge('0','1',90);
    G.addEdge('0','4',75);
    G.addEdge('0','3',10);
    G.addEdge('1','2',30);
    G.addEdge('2','4',10);
    G.addEdge('3','2',30);
    G.addEdge('3','4',10);
    std::cout << "GraphIsConnected " << G.isGraphConnected() << std::endl;
    G.write2Dot("../test06.dot");
    auto min_dist_Graph = G.Bellman_Ford('0');
    for(auto [key,value] : min_dist_Graph){
        std::cout << key << " : " << value << std::endl;
    }
}

void test07()
{
    UnDirGraph<char,int> G({'1','2','3','4','5','6','7'});
    G.addEdge('1','2',2);
    G.addEdge('1','3',4);
    G.addEdge('1','4',1);
    G.addEdge('2','4',3);
    G.addEdge('2','5',10);
    G.addEdge('3','4',2);
    G.addEdge('3','6',5);
    G.addEdge('4','5',7);
    G.addEdge('4','6',8);
    G.addEdge('4','7',4);
    G.addEdge('5','7',6);
    G.addEdge('6','7',1);
    //G.write2Dot("../test07.dot");
    auto min_tree = G.Kruskal();
    //min_tree.print();
    min_tree.write2Dot("../test07_2.dot");
}
void test08()
{
    Graph<char,int> G({'0','1','2','3'});
    G.addEdge('0','1',1);
    G.addEdge('0','2',1);
    G.addEdge('1','3',1);
    G.addEdge('2','1',1);
    G.addEdge('2','3',1);
    G.addEdge('3','2',1);
    G.print();
    // ’2‘到'2'是否连通
    std::cout << "是否连通: " << G.isNodeCycle('3') << std::endl;
    std::cout <<"是否有环: " << G.isDGA() << std::endl;
}

void test09()
{
    Graph<char,int> G({'0','1','2','3','4','5'});
    G.addEdge('0','1',4);
    G.addEdge('0','2',2);
    G.addEdge('1','2',1);
    G.addEdge('1','3',2);
    G.addEdge('1','4',4);
    G.addEdge('2','4',2);
    G.addEdge('3','5',3);
    G.addEdge('4','5',3);
    // G.write2Dot("../test08.dot");
    double Emax = G.Ford_Fulkerson('0','5');
    std::cout << "最大流求解结果是: " << Emax << std::endl;

}

void test10()
{
    Graph<char,int> G({'0','1','2'});
    G.addMatrix({{8,25,50},{50,35,75},{22,48,150}});
    std::cout << "最优解: " << G.naiveHungarianAlgorithm() << std::endl;
}